Date: Tue, 05 Nov 1996 22:04:36 GMT
Server: NCSA/1.5
Content-type: text/html
Last-modified: Thu, 30 May 1996 19:49:55 GMT
Content-length: 3781

<HTML>
<HEAD>
<TITLE>UW Theory Page</TITLE>
</HEAD>

<BODY>
<H1>UW-Madison Theory of Computing Page</H1>

<H4>
Under construction, natch.
Please send corrections, additions, and complaints to 
<!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><!WA0><A HREF="mailto:glaserea@cs.wisc.edu">glaserea@cs.wisc.edu</A>.</H4>


<H2>Faculty</H2>
<UL>
  <LI> <!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><!WA1><A HREF="http://www.cs.wisc.edu/~pubs/faculty-info/bach.html">Eric Bach</A>
  <LI> <!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><!WA2><A HREF="http://www.cs.wisc.edu/~pubs/faculty-info/condon.html">Anne Condon</A>
  <LI> <!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><!WA3><A HREF="http://www.cs.wisc.edu/~pubs/faculty-info/joseph.html">Deborah Joseph</A>
</UL>

<H2>Students</H2>
<UL>
  <LI> Sun Chung
  <LI> Bill Donaldson
  <LI> <!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><!WA4><A HREF="http://www.cs.wisc.edu/~glaserea/glaserea.html">Elton Glaser</A>
  <LI> Amy Hauth
  <LI> <!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><!WA5><A HREF="http://www.cs.wisc.edu/~siff/siff.html">Michael Siff</A>
  <LI> <!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><!WA6><A HREF="http://www.cs.wisc.edu/~watrous/watrous.html">John Watrous</A>
</UL>

<H2>Courses</H2>
<UL>
  <LI> <!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><!WA7><A HREF="http://www.cs.wisc.edu/~pubs/grad-guidebook/node9.html#cs520">520 Introduction to Theoretical Computer Science</A>
  <LI> <!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><!WA8><A HREF="http://www.cs.wisc.edu/~pubs/grad-guidebook/node9.html#cs577">577 Introduction to Algorithms</A>
  <LI> <!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><!WA9><A HREF="http://www.cs.wisc.edu/~pubs/grad-guidebook/node9.html#cs709">709 Mathematical Techniques for Analysis of Algorithms</A>
  <LI> <!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><!WA10><A HREF="http://www.cs.wisc.edu/~pubs/grad-guidebook/node9.html#cs767">767 Graph Theory</A>
  <LI> <!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><!WA11><A HREF="http://www.cs.wisc.edu/~pubs/grad-guidebook/node9.html#cs787">787 Advanced Algorithms and Data Structures</A>
  <LI> <!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><!WA12><A HREF="http://www.cs.wisc.edu/~pubs/grad-guidebook/node9.html#cs810">810 Models and Formalisms for Computation</A>
  <LI> <!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><!WA13><A HREF="http://www.cs.wisc.edu/~pubs/grad-guidebook/node9.html#cs812">812 Arithmetic Algorithms</A>
  <LI> <!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><!WA14><A HREF="http://www.cs.wisc.edu/~pubs/grad-guidebook/node9.html#cs820">820 Theory of Automata and Formal Languages</A>
  <LI> <!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><!WA15><A HREF="http://www.cs.wisc.edu/~pubs/grad-guidebook/node9.html#cs830">830 Abstract and Concrete Complexity Theory</A>
</UL>

<H2>Qualifying Exams</H2>

Theory students thinking about getting a PhD will 
probably be interested in past 
<!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><!WA16><a href="http://www.cs.wisc.edu/~glaserea/uwtheory/quals.html"> 
qualifying exams</a> given in the Theory area, and also the 
<!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><!WA17><a href="http://www.cs.wisc.edu/~glaserea/uwtheory/list.ps">
depth exam syllabus</a>.



<H2>Recent Publications</H2>
<UL>
<!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><!WA18><a href="http://www.cs.wisc.edu/~glaserea/paper.ps"> 
"DNA Models and Algorithms for NP-Complete Problems"</a>,
E. Bach, A. Condon, E. Glaser & C. Tanguay,
to appear in the 1996 <em>IEEE Conference on Computational Complexity</em>. <p>

<EM>Algorithmic Number Theory (Volume I: Efficient Algorithms)</EM>, 
E. Bach & J. Shallit, to appear, MIT Press, Cambridge, MA, March
1996. <P>

<!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><!WA19><a href="http://www.cs.wisc.edu/~watrous/qca.ps"> 
"On One-Dimensional Quantum Cellular Automata"</a>, J.  Watrous,
<em>Symposium on Foundations of Computer Science</em>, 1995.  <p>

"Interactive proof systems with polynomially bounded strategies",
A. Condon & R. Ladner, <EM>Journal of Computer and System Sciences</EM>,
vol. 50, no. 3, 1995. <P>

"Collapsing degrees in subexponential time", D. Joseph, R. Pruim & P.
Young, <EM>Proceedings of the Ninth Structure in Complexity Theory
Conference</EM>, 1994. <P>

</UL>

<H2>Other Assorted Links</H2>
<UL>
    <li> <!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><!WA20><a href="http://www.cs.wisc.edu/"> UW Computer Science</a> department page
    <li> <!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><!WA21><a href="http://www.cs.cmu.edu/~dennis/theory/theory-home.html"> General theory pointers</a>
    <li> <!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><!WA22><a href="http://theory.lcs.mit.edu/"> MIT's theory page</a> 
    <li> <!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><!WA23><a href="http://theory.stanford.edu/"> Stanford's theory page</a> 
    <li> Pictures of <!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><!WA24><a href="http://www.cs.wisc.edu/~glaserea/uwtheory/johnfreak3.gif"> John</a> and
     <!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><!WA25><a href="http://www.cs.wisc.edu/~glaserea/lilblaze.gif"> John's officemate</a> 
</UL>

<HR>
<ADDRESS>
  <!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><!WA26><A HREF="http://www.cs.wisc.edu/~glaserea/glaserea.html">glaserea@cs.wisc.edu</A>
</ADDRESS>
</BODY>
</HTML>
